/*
@Copyright:LintCode
@Author:   tjyemail
@Problem:  http://www.lintcode.com/problem/lowest-common-ancestor
@Language: C++
@Datetime: 16-02-09 05:58
*/

class Solution {
    
    int getpath(TreeNode *root,TreeNode *node,stack<TreeNode*> &s){
		if (root==node) {s.push(root);return 1;}
        if (root==NULL) return 0;
        s.push(root);
        int flag = getpath(root->left,node,s);
        if(flag==1)	return 1;
		else if (flag!=0) s.pop();
        flag = getpath(root->right,node,s);
        if(flag==1) return 1;
		else if (flag!=0) s.pop();
        return -1;
    }
public:
    /**
     * @param root: The root of the binary search tree.
     * @param A and B: two nodes in a Binary.
     * @return: Return the least common ancestor(LCA) of the two nodes.
     */
    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *A, TreeNode *B) {
        // write your code here
		stack<TreeNode*> sa,sb,t;
        
        getpath(root,A,t);
		while(t.size()){
			sa.push(t.top());
			t.pop();
		}

        getpath(root,B,t);		
		while(t.size()){
			sb.push(t.top());
			t.pop();
		}

        while(sa.size() && sb.size() && sa.top()==sb.top()){
            A = sa.top();
            sa.pop();
            sb.pop();
        }
        return A;
    }
};